连连看
最近在玩sumikko farm, 它有一个two turn puzzle相关的活动. 具体如下图![[test.png]] 游戏规则也很简单，就是连接两个相同图案，但确保连接的路径中不能有图案且最多只能有两个turn. 为了做这个活动我绞尽脑汁的玩了一天的puzzle. 但恍惚间我突然意识到，我是一个程序员，为什么不写一个脚本来玩呢？
准备阶段
说干就干，首先不能做一些明显违法的行为比如改数据一类的。那只能模拟自己玩了。这时候我就想到python的pyautogui库. PyAutoGUI lets your Python scripts control the mouse and keyboard to automate interactions with other applications. 这很符合我们的需要，接下来我要做的事情就是直接把puzzle的gameboard数组化，然后跑解就可以了！
gameboard
我是用截图工具找到了puzzle board的左上角和右下角的位置，并使用pillow进行截图, 具体代码如下
from PIL import Image, ImageGrab
IMAGEPOS1 = (294, 453)
IMAGEPOS2 = (1240, 969)
COL = 11
ROW = 6
MAX_TURN = 2
BOXES = 35
PIC_WIDTH = (IMAGEPOS2[0] - IMAGEPOS1[0]) / COL
PIC_HEIGHT = (IMAGEPOS2[1] - IMAGEPOS1[1]) / ROW
image = ImageGrab.grab(bbox=(IMAGEPOS1[0], IMAGEPOS1[1], IMAGEPOS2[0], IMAGEPOS2[1]))
接下来就直接根据行和列拆分每张小图
minigame_board = [[-1] * (COL + 2) for _ in range(ROW + 2)]
for i in range(ROW):
for j in range(COL):
small_image = image.crop((j * PIC_WIDTH, i * PIC_HEIGHT, (j + 1) * PIC_WIDTH, (i + 1) * PIC_HEIGHT))
然后接下来再对比每张图片, 把同类型归项即可。
难点1: 同类型归项
原本准备使用dhash(参考)，因为dhash is good for finding exact duplicates and near duplicates. 但是因为毕竟使用模拟器玩手机 + 使用截图工具手动找到gameboard，这都导致每张小图并不是完美贴合，他们的边距都有些许变化。这导致dhash根本无法使用。
解决思路:
使用opencv-python的template matching. 但这带来了大量工作 ，我需要对每一个类型的图片进行手动的修剪以确保每张图片都能被match. 代码如下:
import cv2
import numpy as np
img = cv2.cvtColor(np.array(img), cv2.COLOR_RGB2BGR)
template = cv2.cvtColor(np.array(template), cv2.COLOR_RGB2BGR)
res = cv2.matchTemplate(img, template, cv2.TM_CCOEFF_NORMED)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)
这样一来对于每张小图, 我只需要比较max_val即可, max_val最高的自然就是match上的。就在我兴高采烈的准备开始写解法的时候，又发现了一个问题。
难点2: 同模不同色
在puzzle中有很多角色的模型一样，颜色也相对接近，比较的时候根本无法分别。
解决思路:
在经过一番查找最后决定再比对一下颜色。
match_area = img[max_loc[1]:max_loc[1]+template.shape[0], max_loc[0]:max_loc[0]+template.shape[1]]
mean1 = cv2.mean(cv2.cvtColor(match_area, cv2.COLOR_BGR2HSV))[:3]
mean2 = cv2.mean(cv2.cvtColor(template, cv2.COLOR_BGR2HSV))[:3]
color_diff = np.linalg.norm(np.array(mean1) - np.array(mean2))
在这里，我们使用之前matchTemplate的返回值来找到图像中最match的地方，并把这一部分截取下来和template做对比。color_diff最低的就是我们想要的图片了
于是经过一番操作，我们终于可以把每张小图都找到他们对应的template，我们再为template取上id，这样每个小图都可以用数字表示。
解法
原本写了bfs，但是跑起来太慢了，目测时间复杂度至少要 。于是还是决定暴力做。 首先我们对于每个template都记录了他们对应的位置，其次我们需要一个function来判断两点是否能连接，代码如下:
def move(board, st, ed):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(x, y, turn, dir):
if x < 0 or x >= ROW + 2 or y < 0 or y >= COL + 2 or turn > MAX_TURN:
return False
if (x, y) == ed:
board[st[0]][st[1]] = -1
board[ed[0]][ed[1]] = -1
return True
if board[x][y] == BOXES or board[x][y] != -1:
return False
for next in directions:
if next == dir:
res = dfs(x + next[0], y + next[1], turn, next)
else:
res = dfs(x + next[0], y + next[1], turn + 1, next)
if res:
return True
return False
for dir in directions:
if dfs(st[0] + dir[0], st[1] + dir[1], 0, dir):
return True
return False
这里我们传入起点和终点, 并往4个方向出发，通过dfs来判断是否能在two turn的limit里连接上。
写完以后我们只需要补充点pyautogui的点击操作就可以开始运行啦！例如:
import pyautogui
def click(x, y):
real_x = IMAGEPOS1[0] + x * PIC_WIDTH + PIC_WIDTH / 2
real_y = IMAGEPOS1[1] + y * PIC_HEIGHT + PIC_HEIGHT / 2
pyautogui.moveTo(real_x, real_y, duration=0.1)
# pyautogui.sleep(0.2)
pyautogui.click()
又比方说可能需要点击某个图标(但图标我们也不知道什么时候出现):
try:
ok_pos = pyautogui.locateCenterOnScreen('./img/ok.png')
if ok_pos:
pyautogui.click(ok_pos)
except:
pass
具体代码请参考two turn puzzle solver